package com.lee.algorithm.linkedlist;

import com.lee.algorithm.linkedlist.struct.OneWayNode;

/***
 * @description: 打印两个有序列表的公共部分
 * @author : 青石路
 * @date: 2021/11/29 21:17
 */
public class PrintTwoListCommon {

    public static void main(String[] args) {
        // one：1 -> 2 -> 5
        // 0 -> 2 -> 3 -> 5 -> 8
        OneWayNode<Integer> head1 = new OneWayNode<Integer>(1);
        OneWayNode<Integer> n2 = new OneWayNode<Integer>(2);
        OneWayNode<Integer> n3 = new OneWayNode<Integer>(5);
        head1.next = n2;
        n2.next = n3;

        OneWayNode<Integer> head2 = new OneWayNode<Integer>(0);
        OneWayNode<Integer> na = new OneWayNode<Integer>(2);
        OneWayNode<Integer> nb = new OneWayNode<Integer>(3);
        OneWayNode<Integer> nc = new OneWayNode<Integer>(5);
        OneWayNode<Integer> nd = new OneWayNode<Integer>(8);
        head2.next = na;
        na.next = nb;
        nb.next = nc;
        nc.next = nd;

        printTwoListCommon(head1, head2);
    }

    /**
     * 给定两个有序链表的头指针 one 和 two，打印两个链表的公共部分
     * one：1 -> 2 -> 5
     * two：0 -> 2 -> 3 -> 5 -> 8
     * 公共部分是：2 和 5
     * 要求：如果两个链表的长度之和为 N，那么时间复杂度要求为 O(N)，额外空间复杂度为 O(1)
     *
     * 类似 归并排序
     *
     * @param one
     * @param two
     */
    public static void printTwoListCommon(OneWayNode<Integer> one, OneWayNode<Integer> two) {
        if (one == null || two == null) {
            return;
        }

        OneWayNode<Integer> cur1 = one;
        OneWayNode<Integer> cur2 = two;
        while (cur1 != null && cur2 != null) {
            if (cur1.value.equals(cur2.value)) {
                System.out.print(cur1.value + " ");
                cur1 = cur1.next;
                cur2 = cur2.next;
            } else if (cur1.value > cur2.value) {
                cur2 = cur2.next;
            } else {
                cur1 = cur1.next;
            }
        }
    }
}
